package com.arron.algorithm.leetcodetop100.动态规划;


import org.omg.CORBA.MARSHAL;

import java.util.Arrays;

/**
 * 64. 最小路径和
 */
public class 最小路径和 {


    int[][] table;

    public  int minPathSum(int[][] grid) {

        table = new int[grid.length+1][grid[0].length+1];

        return minPathSum_dynamic(grid,grid.length-1,grid[0].length-1);
    }

    /**
     * 自顶向下的 ，带记忆的 递归
     * @param grid
     * @param i
     * @param j
     * @return
     */
    public  int minPathSum(int[][] grid,int i,int j) {


        if (i==0 && j ==0){
            return grid[0][0];
        }

        if (i<0 || j<0){
            return Integer.MAX_VALUE;
        }

        if (table[i][j] !=0){
            return table[i][j];
        }

        table[i][j] = Math.min(minPathSum(grid,i-1,j),minPathSum(grid,i,j-1))+grid[i][j];

        return table[i][j];

    }


    /**
     * 自底向上的动态规划
     * @param grid
     * @param i
     * @param j
     * @return
     */
    public  int minPathSum_dynamic(int[][] grid,int i,int j) {

        for (int k = 1; k <= j; k++) {
            grid[0][k] = grid[0][k-1] + grid[0][k];
        }
        for (int k = 1; k <= i; k++) {
            grid[k][0] = grid[k-1][0] + grid[k][0];
        }

        for (int k = 1; k <= i; k++) {
            for (int l = 1; l <=j; l++) {
                grid[k][l] = Math.min(grid[k][l-1],grid[k-1][l])+grid[k][l] ;
            }
        }
        return grid[i][j];
    }


}
